#include <kernel/list.h>
#include <kernel/hash.h>
#include "threads/synch.h"
#include "threads/palloc.h"
#include "threads/malloc.h"
#include "threads/vaddr.h"
#include "userprog/process.h"
#include "userprog/pagedir.h"
#include "vm/frame.h"
#include "vm/swap.h"
#include "vm/page.h"

void frame_init (void)
{
    list_init (&frame_list);
    lock_init (&lockf);
    frame_victim = NULL;
}

struct frame_list_elem* frame_make_new (struct thread* arg_t, void* arg_upage)
{
    struct frame_list_elem* new_frame = (struct frame_list_elem*) malloc (sizeof (struct frame_list_elem));

    if (new_frame != NULL)
    {
       new_frame->id.owner_t = arg_t;
       new_frame->id.upage = arg_upage;

       lock_acquire (&lockf);

       list_push_back (&frame_list, &new_frame->elem); 

       lock_release (&lockf);

       if (frame_victim == NULL)
       {
          frame_victim = new_frame;
       }

       return new_frame;
    }
    else
    {
       return NULL;
    }
}

void frame_remove (struct frame_list_elem* arg_f)
{
    if (frame_victim == arg_f)
    {
        frame_victim_next ();

	if (frame_victim == arg_f)
        {
           frame_victim = NULL;
        }
    }
    list_remove (&arg_f->elem);
    free (arg_f);
}

void frame_remove_all (struct thread* arg_t)
{
    struct list_elem *el, *next_el;
    struct frame_list_elem* temp_frame;

    lock_acquire (&lockf);

    for (el = list_begin (&frame_list); el != list_end (&frame_list); el = next_el)
    {
        temp_frame = list_entry (el, struct frame_list_elem, elem);
        next_el = list_next (el);

        if (arg_t == NULL || temp_frame->id.owner_t == arg_t)
        {
           frame_remove (temp_frame);
        }
    }
    swap_release (arg_t);
    lock_release (&lockf);
}

bool frame_swap_out_ready (struct frame_list_elem* arg_f, bool* want_to_write, uint32_t* arg_wr)
{
    uint32_t i;
    struct page_id prev_id;
    struct page_info* temp_page;

    *want_to_write = false;
    lock_acquire(&lockf);

    if (pagedir_is_dirty (arg_f->id.owner_t->pagedir, arg_f->id.upage))
    {
        if (!swap_allocate(&arg_f->id, &prev_id, &i))
        {
	   lock_release (&lockf);
           return false;
        }
        
        if (prev_id.owner_t != arg_f->id.owner_t || prev_id.upage != arg_f->id.upage)
        {
           if (prev_id.owner_t != NULL)
           {
              pagedir_set_dirty (prev_id.owner_t->pagedir, prev_id.upage, true);
           }
        }

        *want_to_write = true;
        *arg_wr = i;
    }
    else
    {
        swap_allocate (&arg_f->id, &prev_id, &i);
    }
    lock_release (&lockf);

    pagedir_clear_page (arg_f->id.owner_t->pagedir, arg_f->id.upage);
    return true;
}

void* frame_load (struct page_id* temp_pid)
{
    if (temp_pid->upage == NULL || !is_valid_addr_when_stack_grow (temp_pid->upage, 1, false) 
       || pg_ofs (temp_pid->upage) != 0)
    {
       return NULL;
    }

    void* kpage = palloc_get_page_not_load (PAL_USER);
    bool want_to_write = false;
    uint32_t wr;    

    if (kpage == NULL)
    {    
	lock_acquire(&thread_current()->fm_lock);
        struct frame_list_elem* temp_frame = frame_select_victim ();
        lock_release(&thread_current()->fm_lock);

        if (temp_frame == NULL)
        {	
           return NULL;
        }
       
        kpage = pagedir_get_page (temp_frame->id.owner_t->pagedir, temp_frame->id.upage);
         
        if (!frame_swap_out_ready (temp_frame, &want_to_write, &wr))
        {
           return NULL;
        }

        temp_frame->id.owner_t = temp_pid->owner_t;
        temp_frame->id.upage = temp_pid->upage;
    }
    else
    {
        struct frame_list_elem* temp_frame = frame_make_new (temp_pid->owner_t, temp_pid->upage);

        if (temp_frame == NULL)
        {
	   return NULL;
        }
    }
  
    lock_acquire (&lockf);

    if (want_to_write)
    {
       swap_out (wr, kpage);
    }

    swap_load (temp_pid, kpage);
    
    struct thread* temp_t = temp_pid->owner_t;
    void* temp_upage = temp_pid->upage;

    pagedir_set_dirty (temp_t->pagedir, temp_upage, false);
    pagedir_set_accessed (temp_t->pagedir, temp_upage, true);
    pagedir_set_page (temp_t->pagedir, temp_upage, kpage, 
                      pagedir_can_write (temp_t->pagedir, temp_upage));

    lock_release (&lockf);

    return kpage;
}

void* frame_load_new ()
{   
    struct frame_list_elem* temp_frame = frame_select_victim ();

    if (temp_frame == NULL)
    {
       return NULL;
    }

    void* kpage = pagedir_get_page (temp_frame->id.owner_t->pagedir, temp_frame->id.upage);
    bool want_to_write = false;
    uint32_t wr;

    if (!frame_swap_out_ready (temp_frame, &want_to_write, &wr))
    {
       return NULL;
    }

    lock_acquire (&lockf);
    frame_remove (temp_frame);
    
    if (want_to_write)
    {
       swap_out (wr, kpage);
    }

    lock_release (&lockf);
    return kpage;
}

void frame_victim_next ()
{
    if (frame_victim == NULL)
    {
       return;
    }

    frame_victim = list_entry (list_next (&frame_victim->elem), struct frame_list_elem, elem);

    if (&frame_victim->elem == list_end (&frame_list))
    {
       frame_victim = list_entry (list_begin (&frame_list), struct frame_list_elem, elem);
    }
}

struct frame_list_elem* frame_select_victim ()
{
    struct frame_list_elem* temp_frame = NULL;

    if (frame_victim == NULL)
    {
       frame_victim = list_entry (list_front (&frame_list), struct frame_list_elem, elem);
    }
    while (pagedir_is_accessed (frame_victim->id.owner_t->pagedir, frame_victim->id.upage))
    {
       pagedir_set_accessed (frame_victim->id.owner_t->pagedir, frame_victim->id.upage, false);
       frame_victim_next ();
    }
    temp_frame = frame_victim;
    frame_victim_next ();

    return temp_frame;
}
